/* 第一部分：C代码声明，放在 %{ ... %} 中 */
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#ifdef _WIN32
#define strdup _strdup
#endif

// DAG节点结构
struct DAGNode {
    char op[10];
    char arg1[20];
    char arg2[20];
    char result[20];
    int visited;
    int id;
    struct DAGNode* left;   // 添加左子节点
    struct DAGNode* right;  // 添加右子节点
};

// 四元式结构
struct Quadruple {
    char op[10];
    char arg1[20];
    char arg2[20];
    char result[20];
};

// Loop结构
struct Loop {
    int header;         // 循环头
    int end;           // 循环尾
    int *body;         // 循环体中的四元式索引
    int body_size;     // 循环体大小
    char *init_var;    // 循环初始化变量
    char *counter;     // 循环计数器
    int step;          // 步长
    int limit;         // 循环限制值
    int parent;        // 父循环索引
    bool is_nested;    // 是否是嵌套循环
    int init_quad;     // 初始化四元式的位置
    int update_quad;   // 更新四元式的位置
    struct Quadruple* invariant_code; // 循环不变代码
    int invariant_count;              // 不变代码数量
};

void yyerror(const char *s);
int yylex(void);

/* 符号表结构 */
struct symbol {
    char *name;
    int type;    // 0: int, 1: float
    double value;
};

#define NSYMS 100     /* 符号表大小 */
struct symbol symtab[NSYMS];
int sym_count = 0;    /* 符号表中的符号数量 */

/* 四元式序列 */
struct Quadruple quadruples[100];
int quad_count = 0;

/* 存储优化后的四元式 */
struct Quadruple optimized_quads[100];
int optimized_quad_count = 0;

/* 基本块标记数组 */
char is_leader[100] = {0};

/* 全局变量 */
int temp_var_count = 0;  // 用于生成临时变量名

/* 函数声明 */
void print_quadruple(struct Quadruple q);
char* new_temp(void);
void generate_quad(char *op, char *arg1, char *arg2, char *result);
void print_quads(void);
struct DAGNode* find_dag_node(struct DAGNode *dag, int dag_size, char *op, char *arg1, char *arg2);
void build_dag(int start, int end, struct DAGNode *dag, int *dag_size);
void optimize_dag(struct DAGNode *dag, int dag_size);
void print_optimized_quads(void);
void find_loops(struct Loop* loops, int* num_loops);
void loop_invariant_code_motion(struct Loop* loop);
void strength_reduction(struct Loop* loop);
void induction_variable_elimination(struct Loop* loop);
void insert_quadruple(int position, const char* op, const char* arg1, const char* arg2, const char* result);

/* 生成标签 */
char* new_label() {
    static int label_count = 0;
    char* label = (char*)malloc(20);
    sprintf(label, "L%d", label_count++);
    return label;
}

/* 查找符号 */
struct symbol* lookup(char* name) {
    for(int i = 0; i < sym_count; i++) {
        if(strcmp(symtab[i].name, name) == 0) {
            return &symtab[i];
        }
    }
    return NULL;
}

/* 添加符号 */
void add_symbol(char* name, int type) {
    if(sym_count < NSYMS) {
        symtab[sym_count].name = strdup(name);
        symtab[sym_count].type = type;
        symtab[sym_count].value = 0;
        sym_count++;
    }
}

/* 函数实现 */
void print_quadruple(struct Quadruple q) {
    printf("%s, %s, %s, %s\n", q.op, q.arg1, q.arg2, q.result);
}

/* 生成临时变量名 */
char* new_temp() {
    static int temp_count = 0;
    char* temp = (char*)malloc(20);
    sprintf(temp, "t%d", temp_count++);
    return temp;
}

/* 添加四元式 */
void generate_quad(char *op, char *arg1, char *arg2, char *result) {
    strcpy(quadruples[quad_count].op, op);
    strcpy(quadruples[quad_count].arg1, arg1);
    strcpy(quadruples[quad_count].arg2, arg2);
    strcpy(quadruples[quad_count].result, result);
    quad_count++;
}

/* 输出所有四元式 */
void print_quads() {
    for (int i = 0; i < quad_count; i++) {
        print_quadruple(quadruples[i]);
    }
}

/* 构建基本块的DAG */
void build_dag(int start, int end, struct DAGNode *dag, int *dag_size) {
    *dag_size = 0;
    for (int i = start; i <= end && i < quad_count; i++) {
        if (strcmp(quadruples[i].op, "+") == 0 || strcmp(quadruples[i].op, "-") == 0 ||
            strcmp(quadruples[i].op, "*") == 0 || strcmp(quadruples[i].op, "/") == 0) {
            struct DAGNode *existing_node = find_dag_node(dag, *dag_size, quadruples[i].op, quadruples[i].arg1, quadruples[i].arg2);
            if (existing_node != NULL) {
                strcpy(existing_node->result, quadruples[i].result);
                continue;
            }
            strcpy(dag[*dag_size].op, quadruples[i].op);
            strcpy(dag[*dag_size].arg1, quadruples[i].arg1);
            strcpy(dag[*dag_size].arg2, quadruples[i].arg2);
            strcpy(dag[*dag_size].result, quadruples[i].result);
            dag[*dag_size].visited = 0;
            dag[*dag_size].id = *dag_size;
            (*dag_size)++;
        } else if (strcmp(quadruples[i].op, "=") == 0) {
            for (int j = 0; j < *dag_size; j++) {
                if (strcmp(dag[j].result, quadruples[i].arg1) == 0) {
                    strcpy(dag[j].result, quadruples[i].result);
                    break;
                }
            }
        }
    }
}

/* 查找DAG中已存在的节点 */
struct DAGNode* find_dag_node(struct DAGNode *dag, int dag_size, char *op, char *arg1, char *arg2) {
    for (int i = 0; i < dag_size; i++) {
        if (strcmp(dag[i].op, op) == 0 && strcmp(dag[i].arg1, arg1) == 0 && strcmp(dag[i].arg2, arg2) == 0) {
            return &dag[i];
        }
    }
    return NULL;
}

/* 改进的DAG优化函数 */
void optimize_dag(struct DAGNode *dag, int dag_size) {
    printf("\nDAG Optimization Results:\n");
    
    // 创建一个数组标记哪些四元式被优化了
    bool optimized[100] = {false};
    optimized_quad_count = 0;
    
    // 首先添加优化后的四元式
    for (int i = 0; i < dag_size; i++) {
        if (strlen(dag[i].op) > 0) {
            strcpy(optimized_quads[optimized_quad_count].op, dag[i].op);
            strcpy(optimized_quads[optimized_quad_count].arg1, dag[i].arg1);
            strcpy(optimized_quads[optimized_quad_count].arg2, dag[i].arg2);
            strcpy(optimized_quads[optimized_quad_count].result, dag[i].result);
            optimized_quad_count++;
            
            // 标记被优化的四元式
            for (int j = 0; j < quad_count; j++) {
                if (strcmp(quadruples[j].result, dag[i].result) == 0) {
                    optimized[j] = true;
                }
            }
        }
    }
    
    // 添加未被优化的四元式
    for (int i = 0; i < quad_count; i++) {
        if (!optimized[i]) {
            optimized_quads[optimized_quad_count++] = quadruples[i];
        }
    }
    
    printf("Complete optimized quadruples (including unoptimized parts):\n");
    for (int i = 0; i < optimized_quad_count; i++) {
        printf("L%d: ", i);
        print_quadruple(optimized_quads[i]);
    }
}

/* 打印优化后的四元式 */
void print_optimized_quads() {
    for (int i = 0; i < optimized_quad_count; i++) {
        printf("    ");
        print_quadruple(optimized_quads[i]);
    }
}

/* 添加辅助函数 */
bool is_constant(const char* str) {
    return str[0] >= '0' && str[0] <= '9';
}

bool is_temp_var(const char* str) {
    return str[0] == 't';
}

char* get_real_var(const char* temp_var, int current_pos) {
    for (int i = current_pos - 1; i >= 0; i--) {
        if (strcmp(quadruples[i].result, temp_var) == 0) {
            return quadruples[i].arg1;
        }
    }
    return NULL;
}

/* 改进的循环识别函数 */
void find_loops(struct Loop* loops, int* num_loops) {
    *num_loops = 0;
    
    for (int i = 0; i < quad_count; i++) {
        // 识别循环条件语句
        if (strcmp(quadruples[i].op, "<") == 0 || 
            strcmp(quadruples[i].op, ">") == 0 ||
            strcmp(quadruples[i].op, "<=") == 0 ||
            strcmp(quadruples[i].op, ">=") == 0) {
            
            // 向后查找goto指令
            for (int j = i + 1; j < quad_count; j++) {
                if (strcmp(quadruples[j].op, "goto") == 0) {
                    // 初始化循环结构
                    loops[*num_loops].header = i;
                    loops[*num_loops].end = j;
                    loops[*num_loops].body = (int*)malloc(sizeof(int) * (j - i + 1));
                    loops[*num_loops].body_size = 0;
                    loops[*num_loops].parent = -1;
                    loops[*num_loops].is_nested = false;
                    loops[*num_loops].invariant_code = (struct Quadruple*)malloc(sizeof(struct Quadruple) * 100);
                    loops[*num_loops].invariant_count = 0;
                    
                    // 识别循环变量
                    loops[*num_loops].counter = strdup(quadruples[i].arg1);
                    
                    // 查找循环变量初始化
                    for (int k = 0; k < i; k++) {
                        if (strcmp(quadruples[k].op, "=") == 0 && 
                            strcmp(quadruples[k].result, loops[*num_loops].counter) == 0) {
                            loops[*num_loops].init_var = strdup(quadruples[k].arg1);
                            loops[*num_loops].init_quad = k;
                            break;
                        }
                    }
                    
                    // 识别循环限制值
                    if (is_constant(quadruples[i].arg2)) {
                        loops[*num_loops].limit = atoi(quadruples[i].arg2);
                    }
                    
                    // 识别步长和更新位置
                    for (int k = i + 1; k < j; k++) {
                        if ((strcmp(quadruples[k].op, "+") == 0 || 
                             strcmp(quadruples[k].op, "-") == 0) &&
                            strcmp(quadruples[k].result, loops[*num_loops].counter) == 0) {
                            loops[*num_loops].step = atoi(quadruples[k].arg2);
                            loops[*num_loops].update_quad = k;
                            break;
                        }
                    }
                    
                    // 收集循环体
                    for (int k = i + 1; k < j; k++) {
                        loops[*num_loops].body[loops[*num_loops].body_size++] = k;
                    }
                    
                    printf("\nFound Loop %d:\n", *num_loops);
                    printf("  Header: L%d\n", loops[*num_loops].header);
                    printf("  Counter: %s\n", loops[*num_loops].counter);
                    printf("  Init: %s (at L%d)\n", loops[*num_loops].init_var, loops[*num_loops].init_quad);
                    printf("  Step: %d (at L%d)\n", loops[*num_loops].step, loops[*num_loops].update_quad);
                    printf("  Body size: %d\n", loops[*num_loops].body_size);
                    
                    (*num_loops)++;
                    break;
                }
            }
        }
    }
    
    // 识别嵌套关系
    for (int i = 0; i < *num_loops; i++) {
        for (int j = 0; j < *num_loops; j++) {
            if (i != j && 
                loops[j].header > loops[i].header && 
                loops[j].end < loops[i].end) {
                loops[j].parent = i;
                loops[j].is_nested = true;
                printf("Loop %d is nested inside Loop %d\n", j, i);
            }
        }
    }
}

/* 改进的循环不变代码外提 */
void loop_invariant_code_motion(struct Loop* loop) {
    printf("\nLoop Invariant Code Motion Analysis:\n");
    
    // 显示原始循环代码
    printf("Original loop code:\n");
    for (int i = 0; i < loop->body_size; i++) {
        int idx = loop->body[i];
        printf("L%d: ", idx);
        print_quadruple(quadruples[idx]);
    }
    
    // 识别循环不变代码
    for (int i = 0; i < loop->body_size; i++) {
        int idx = loop->body[i];
        struct Quadruple* quad = &quadruples[idx];
        
        bool is_invariant = true;
        
        // 检查操作数是否在循环中被修改
        if (strcmp(quad->op, "+") == 0 || strcmp(quad->op, "*") == 0 ||
            strcmp(quad->op, "-") == 0 || strcmp(quad->op, "/") == 0) {
            
            for (int j = 0; j < loop->body_size; j++) {
                int check_idx = loop->body[j];
                if (strcmp(quadruples[check_idx].result, quad->arg1) == 0 ||
                    strcmp(quadruples[check_idx].result, quad->arg2) == 0) {
                    is_invariant = false;
                    break;
                }
            }
            
            if (is_invariant) {
                printf("Found invariant computation at L%d: ", idx);
                print_quadruple(*quad);
                
                // 保存不变代码
                loop->invariant_code[loop->invariant_count++] = *quad;
                
                // 创建临时变量
                char* temp = new_temp();
                
                // 循环前插入不变计算
                insert_quadruple(loop->header, 
                               quad->op, 
                               quad->arg1, 
                               quad->arg2, 
                               temp);
                
                // 在循环中使用临时变量
                strcpy(quad->op, "=");
                strcpy(quad->arg1, temp);
                strcpy(quad->arg2, "");
            }
        }
    }
    
    printf("\nOptimized loop code:\n");
    for (int i = loop->header; i <= loop->end; i++) {
        printf("L%d: ", i);
        print_quadruple(quadruples[i]);
    }
}

/* 改进的强度削弱优化 */
void strength_reduction(struct Loop* loop) {
    printf("\nStrength Reduction Analysis:\n");
    
    // 显示原始代码
    printf("Original code:\n");
    for (int i = 0; i < loop->body_size; i++) {
        int idx = loop->body[i];
        printf("L%d: ", idx);
        print_quadruple(quadruples[idx]);
    }
    
    // 遍历循环体中的每条指令
    for (int i = 0; i < loop->body_size; i++) {
        int idx = loop->body[i];
        struct Quadruple* quad = &quadruples[idx];
        
        // 乘法优化为移位
        if (strcmp(quad->op, "*") == 0 && is_constant(quad->arg2)) {
            int value = atoi(quad->arg2);
            if ((value & (value - 1)) == 0) {  // 是2的幂
                int shift = 0;
                while (value > 1) {
                    shift++;
                    value >>= 1;
                }
                
                printf("Converting multiplication at L%d to shift: ", idx);
                print_quadruple(*quad);
                
                char shift_str[20];
                sprintf(shift_str, "%d", shift);
                strcpy(quad->op, "<<");
                strcpy(quad->arg2, shift_str);
            }
        }
        // 除法优化为移位
        else if (strcmp(quad->op, "/") == 0 && is_constant(quad->arg2)) {
            int value = atoi(quad->arg2);
            if ((value & (value - 1)) == 0) {  // 是2的幂
                int shift = 0;
                while (value > 1) {
                    shift++;
                    value >>= 1;
                }
                
                printf("Converting division at L%d to shift: ", idx);
                print_quadruple(*quad);
                
                char shift_str[20];
                sprintf(shift_str, "%d", shift);
                strcpy(quad->op, ">>");
                strcpy(quad->arg2, shift_str);
            }
        }
    }
    
    printf("\nOptimized code:\n");
    for (int i = loop->header; i <= loop->end; i++) {
        printf("L%d: ", i);
        print_quadruple(quadruples[i]);
    }
}

/* 改进的归纳变量优化 */
void induction_variable_elimination(struct Loop* loop) {
    printf("\nInduction Variable Analysis:\n");
    
    // 识别基本归纳变量
    char* basic_induction_vars[100];
    int basic_count = 0;
    
    for (int i = 0; i < loop->body_size; i++) {
        int idx = loop->body[i];
        if (strcmp(quadruples[idx].op, "+") == 0 && 
            strcmp(quadruples[idx].result, quadruples[idx].arg1) == 0) {
            basic_induction_vars[basic_count++] = strdup(quadruples[idx].result);
            printf("Found basic induction variable: %s\n", quadruples[idx].result);
        }
    }
    
    // 识别并优化派生归纳变量
    for (int i = 0; i < loop->body_size; i++) {
        int idx = loop->body[i];
        for (int j = 0; j < basic_count; j++) {
            if (strcmp(quadruples[idx].arg1, basic_induction_vars[j]) == 0 ||
                strcmp(quadruples[idx].arg2, basic_induction_vars[j]) == 0) {
                printf("Found derived induction variable at L%d: ", idx);
                print_quadruple(quadruples[idx]);
                
                // 这里可以添加派生归纳变量的优化逻辑
            }
        }
    }
}

/* 插入四元式 */
void insert_quadruple(int position, const char* op, const char* arg1, const char* arg2, const char* result) {
    // 将position之后的四元式向后移动一位
    for (int i = quad_count; i > position; i--) {
        quadruples[i] = quadruples[i-1];
    }
    
    // 在position处插入新的四元式
    strcpy(quadruples[position].op, op);
    strcpy(quadruples[position].arg1, arg1);
    strcpy(quadruples[position].arg2, arg2);
    strcpy(quadruples[position].result, result);
    
    quad_count++;
}

/* 改进的循环优化处理函数 */
void process_loop_optimizations(struct Loop* loops, int num_loops) {
    if (num_loops > 0) {
        // 创建一个临时数组存储完整的优化后四元式
        struct Quadruple final_quads[100];
        int final_count = 0;
        
        // 复制DAG优化后的四元式到临时数组
        for (int i = 0; i < optimized_quad_count; i++) {
            final_quads[final_count++] = optimized_quads[i];
        }
        
        // 对每个循环进行优化
        for (int i = 0; i < num_loops; i++) {
            printf("\nOptimizing Loop %d:\n", i + 1);
            
            // 显示原始循环代码
            printf("Original loop code:\n");
            for (int j = loops[i].header; j <= loops[i].end; j++) {
                printf("L%d: ", j);
                print_quadruple(final_quads[j]);
            }
            
            // 应用循环优化
            loop_invariant_code_motion(&loops[i]);
            strength_reduction(&loops[i]);
            induction_variable_elimination(&loops[i]);
            
            // 更新最终的四元式序列
            for (int j = loops[i].header; j <= loops[i].end; j++) {
                final_quads[j] = quadruples[j];
            }
        }
        
        // 显示最终完整的优化结果
        printf("\nFinal Complete Optimized Code:\n");
        for (int i = 0; i < final_count; i++) {
            printf("L%d: ", i);
            print_quadruple(final_quads[i]);
        }
    } else {
        printf("No loops found in the code.\n");
    }
}

%}

/* 第二部分：Bison声明 */
%union {
    double num;
    char *str;
    char *temp;
    struct {
        char *true_label;
        char *false_label;
        char *next_label;
    } labels;
}

/* Token定义 */
%token EOL UMINUS
%token VOID MAIN FOR
%token <num> NUMBER
%token <str> IDENTIFIER
%token ASSIGN INT FLOAT IF ELSE WHILE
%token SEMICOLON LPAREN RPAREN LBRACE RBRACE COMMA

/* 运算符优先级 */
%left GT LT EQ NE GE LE
%left '+' '-'
%left '*' '/'
%nonassoc UMINUS

/* 非终结符类型声明 */
%type <temp> expr term factor
%type <labels> condition
%type <str> declaration
%type <temp> assignment
%type <temp> for_init for_update
%type <temp> init_list
%type <str> id_list

/* 第三部分：语法规则，必须在 %% 之后 */
%%

program:
    function    { 
        printf("\n=== Starting Program Analysis ===\n");
        printf("Program parsed successfully\n"); 
        printf("Semantic analysis completed\n");
        printf("Quadruples generated:\n");
        print_quads();
    }
    ;

function:
    VOID MAIN LPAREN RPAREN block {
        printf("Function 'main' parsed successfully\n");
    }
    ;

block:
    LBRACE statement_list RBRACE {
        printf("Block parsed with statements\n");
    }
    | LBRACE RBRACE {
        printf("Empty block parsed\n");
    }
    ;

statement_list:
    statement {
        printf("Single statement parsed\n");
    }
    | statement_list statement {
        printf("Multiple statements parsed\n");
    }
    | statement_list assignment SEMICOLON {
        printf("Additional assignment statement parsed\n");
    }
    ;

statement:
    declaration SEMICOLON
    | assignment SEMICOLON
    | if_statement
    | while_statement
    | for_statement
    | block
    | EOL
    ;

declaration:
    INT id_list    { $$ = $2; }
    ;

id_list:
    IDENTIFIER {
        printf("Declaration: int %s\n", $1);
        add_symbol($1, 0);
        $$ = $1;
    }
    | id_list COMMA IDENTIFIER {
        printf("Multiple declaration: int %s\n", $3);
        add_symbol($3, 0);
        $$ = $3;
    }
    ;

assignment:
    IDENTIFIER ASSIGN expr    { 
        printf("Assignment to %s\n", $1);
        struct symbol* sym = lookup($1);
        if(sym != NULL) {
            generate_quad("=", $3, "", $1);
            $$ = $1;
        } else {
            yyerror("Undefined variable");
            $$ = "";
        }
    }
    ;

init_list:
    assignment { $$ = $1; }
    | declaration { $$ = $1; }
    | init_list SEMICOLON assignment {
        generate_quad("=", $3, "", "");
        $$ = $3;
    }
    | init_list SEMICOLON declaration {
        generate_quad("=", $3, "", "");
        $$ = $3;
    }
    ;

for_init:
    assignment
    | declaration
    ;

for_update:
    IDENTIFIER ASSIGN expr    { 
        printf("Semantic analysis: updating variable %s\n", $1);
        struct symbol* sym = lookup($1);
        if(sym != NULL) {
            generate_quad("=", $3, "", $1);
            $$ = $1;
        } else {
            yyerror("Undefined variable");
            $$ = "";
        }
    }
    | IDENTIFIER ASSIGN IDENTIFIER '+' NUMBER {
        struct symbol* sym = lookup($1);
        if(sym != NULL) {
            char* temp = new_temp();
            char num_str[20];
            sprintf(num_str, "%g", $5);
            generate_quad("+", $3, num_str, temp);
            generate_quad("=", temp, "", $1);
            $$ = $1;
        } else {
            yyerror("Undefined variable");
            $$ = "";
        }
    }
    | IDENTIFIER ASSIGN IDENTIFIER '-' NUMBER {
        struct symbol* sym = lookup($1);
        if(sym != NULL) {
            char* temp = new_temp();
            char num_str[20];
            sprintf(num_str, "%g", $5);
            generate_quad("-", $3, num_str, temp);
            generate_quad("=", temp, "", $1);
            $$ = $1;
        } else {
            yyerror("Undefined variable");
            $$ = "";
        }
    }
    ;

if_statement:
    IF LPAREN condition RPAREN statement {
        generate_quad("label", "", "", $3.true_label);
        generate_quad("label", "", "", $3.false_label);
    }
    | IF LPAREN condition RPAREN statement ELSE statement {
        char* end_label = new_label();
        generate_quad("label", "", "", $3.true_label);
        generate_quad("goto", "", "", end_label);
        generate_quad("label", "", "", $3.false_label);
        generate_quad("label", "", "", end_label);
    }
    ;

while_statement:
    WHILE LPAREN condition RPAREN statement {
        char* start_label = new_label();
        generate_quad("label", "", "", start_label);
        generate_quad("label", "", "", $3.true_label);
        generate_quad("goto", "", "", start_label);
        generate_quad("label", "", "", $3.false_label);
    }
    ;

for_statement:
    FOR LPAREN for_init SEMICOLON condition SEMICOLON for_update RPAREN statement {
        printf("\n=== Processing FOR loop ===\n");
        char* start_label = new_label();
        char* update_label = new_label();
        char* end_label = new_label();
        printf("Generated labels: start=%s, update=%s, end=%s\n", 
               start_label, update_label, end_label);
        
        generate_quad("label", "", "", start_label);
        generate_quad("if", $5.true_label, "", "");
        generate_quad("if==0", "", "", end_label);
        generate_quad("label", "", "", update_label);
        generate_quad("goto", "", "", start_label);
        generate_quad("label", "", "", end_label);
        printf("FOR loop quadruples generated\n");
    }
    ;

condition:
    expr GT expr     {
        printf("Condition: %s > %s\n", $1, $3);
        $$.true_label = new_label();
        $$.false_label = new_label();
        generate_quad(">", $1, $3, $$.true_label);
        generate_quad("goto", "", "", $$.false_label);
    }
    | expr LT expr   {
        printf("Condition: %s < %s\n", $1, $3);
        $$.true_label = new_label();
        $$.false_label = new_label();
        generate_quad("<", $1, $3, $$.true_label);
        generate_quad("goto", "", "", $$.false_label);
    }
    | expr GE expr   {
        printf("Condition: %s >= %s\n", $1, $3);
        $$.true_label = new_label();
        $$.false_label = new_label();
        generate_quad(">=", $1, $3, $$.true_label);
        generate_quad("goto", "", "", $$.false_label);
    }
    | expr LE expr   {
        printf("Condition: %s <= %s\n", $1, $3);
        $$.true_label = new_label();
        $$.false_label = new_label();
        generate_quad("<=", $1, $3, $$.true_label);
        generate_quad("goto", "", "", $$.false_label);
    }
    ;

expr:
    term                { $$ = $1; }
    | expr '+' term     { 
        char* temp = new_temp();
        generate_quad("+", $1, $3, temp);
        $$ = temp;
    }
    | expr '-' term     { 
        char* temp = new_temp();
        generate_quad("-", $1, $3, temp);
        $$ = temp;
    }
    ;

term:
    factor              { $$ = $1; }
    | term '*' factor   { 
        char* temp = new_temp();
        generate_quad("*", $1, $3, temp);
        $$ = temp;
    }
    | term '/' factor   { 
        char* temp = new_temp();
        generate_quad("/", $1, $3, temp);
        $$ = temp;
    }
    ;

factor:
    NUMBER          { 
        char* temp = new_temp();
        char num_str[20];
        sprintf(num_str, "%g", $1);
        generate_quad("=", num_str, "", temp);
        $$ = temp;
    }
    | IDENTIFIER    { 
        printf("Semantic analysis: reading variable %s\n", $1);
        struct symbol* sym = lookup($1);
        if(sym != NULL) {
            char* temp = new_temp();
            generate_quad("=", $1, "", temp);
            $$ = temp;
        } else {
            yyerror("Undefined variable");
            $$ = "";
        }
    }
    | LPAREN expr RPAREN    { $$ = $2; }
    | '-' factor %prec UMINUS   { 
        char* temp = new_temp();
        generate_quad("-", "0", $2, temp);
        $$ = temp;
    }
    ;

%%

/* 第四部分：C代码实现，包括 main 函数和 yyerror */
void yyerror(const char *s) {
    printf("\n=== Error Detected ===\n");
    fprintf(stderr, "Syntax Error: %s\n", s);
    if (strstr(s, "syntax error")) {
        printf("Current parsing state:\n");
        printf("Last successful token: %s\n", yylval.str ? yylval.str : "unknown");
        fprintf(stderr, "Possible causes:\n");
        fprintf(stderr, "1. Missing semicolon\n");
        fprintf(stderr, "2. Unmatched parentheses or braces\n");
        fprintf(stderr, "3. Invalid operator usage\n");
        fprintf(stderr, "4. Undefined variables\n");
        fprintf(stderr, "5. Multiple assignments not properly separated\n");
    }
}

int main(void) {
    printf("\n=== Starting Compiler ===\n");
    printf("Waiting for input...\n");
    
    // 语法分析
    if (yyparse() != 0) {
        printf("\n=== Parsing Failed ===\n");
        fprintf(stderr, "Syntax error detected in the input program!\n");
        return 1;
    }
    
    printf("\n=== Parsing Completed Successfully ===\n");
    printf("\n=== Original Quadruples ===\n");
    print_quads();
    
    // DAG优���
    printf("\n=== DAG Optimization ===\n");
    struct DAGNode dag[100];
    int dag_size = 0;
    build_dag(0, quad_count-1, dag, &dag_size);
    optimize_dag(dag, dag_size);
    
    // 循环优化
    printf("\n=== Loop Optimization ===\n");
    struct Loop loops[100];
    int num_loops = 0;
    find_loops(loops, &num_loops);
    process_loop_optimizations(loops, num_loops);
    
    return 0;
}